package com.ewivt.excel.algorithm;

import com.alibaba.excel.EasyExcel;
import com.ewivt.excel.model.*;
import com.ewivt.excel.utils.ArrayUtils;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.BeanUtils;
import org.springframework.stereotype.Component;

import javax.annotation.PostConstruct;
import java.time.LocalTime;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

@Slf4j
@Component
public class MutiCarTypeAlgorithm {
    private int index_tmp=0;

    private int count = 0;

    //弧间最短距离矩阵
    private double[][] arcDistanceArray;

    //与arc邻接的矩阵
    private double[][] distanceArray;

    //arc矩阵，记录了原始文件中每条弧及其反向弧的数据
    private double[][] arcsArray;

    //nodes就只是我们给每个点建的一套新的索引
    private double[] nodes;

    //加水点编码,加水点能否使用与车型有关
    private Integer[][] AP1;

    //全天都开的排污点编码
    private Integer[] IF;

    //不是全天都开的排污点编号
    private Integer[] IF1;

    private List<Integer> required_arc;

    //复制一个required_arc
    private List<Integer> counst_required;

    private double nonservice_speed = 40;

    private double L = 7;

    private Integer depot = 0;

    private List<Integer> cind_required_arc;

    private Double[] lamdaap;

    private Double[] lamdaif;

    private Double[] Q1;

    private Double[] Q2;

    private List<Double> all_arc;

    private List<Integer> ind_required_arc;

    private int ind_depot;

    private List<Integer> ind_AP;

    private List<Integer> ind_IF;

    private List<Integer> ind_IF1;

    private List<Double> water_load = new ArrayList<>();

    private List<List<List<Integer>>> T  = new ArrayList<>();

    private List<Double> map_ = new ArrayList<>();

    private List<Double> map_1 = new ArrayList<>();

    private List<Double> map_2 = new ArrayList<>();

    private List<Double> map_3 = new ArrayList<>();

    private List<LinkedHashMap<Double,List<List<Integer>>>> dict_m = new ArrayList<>();

    private LinkedHashMap<Double,List<List<Integer>>> dict_m1 = new LinkedHashMap<>();

    private LinkedHashMap<Double,List<List<Integer>>> dict_m2 = new LinkedHashMap<>();

    private LinkedHashMap<Double,List<List<Integer>>> dict_m3 = new LinkedHashMap<>();

    private List<Double> cm = new ArrayList<>();

    private List<Double> cm1 = new ArrayList<>();

    private List<Double> cm2 = new ArrayList<>();

    private List<Double> cm3 = new ArrayList<>();

    private List<Map<Double,List<List<Integer>>>> cdm = new ArrayList<>();

    private LinkedHashMap<Double,List<List<Integer>>> cdm1 = new LinkedHashMap<>();

    private LinkedHashMap<Double,List<List<Integer>>> cdm2 = new LinkedHashMap<>();

    private LinkedHashMap<Double,List<List<Integer>>> cdm3 = new LinkedHashMap<>();

    private List<Double> typecar_list = new ArrayList<>();

    private List<Double> sametypeDouble = new ArrayList<>();

    private List<Integer> sametype = new ArrayList<>();

    private int x = 0;

    private int t = 0;

    private List<Double> bestcost = new ArrayList<>();

    private List<List<Integer>> pap = new ArrayList<>();

    private List<List<List<Integer>>> T1 = new ArrayList<>();

    private List<CarInfo> catExcelList;

    private List<List<Integer>> P_AP = new ArrayList<>();

    private int ta = 0;

    private List<Integer> indexList = new ArrayList<>();

    private int initNumberOfSides =0;

    private List<Road> roadExcelList;

    @PostConstruct
    public void init(){
        getIndexList();
        String locationExcelFile = "C:\\Users\\徐成超\\Desktop\\code\\算法2\\加了更多约束的数据集.xlsx";
        //道路信息
        roadExcelList = EasyExcel.read(locationExcelFile).head(Road.class).sheet("道路信息").doReadSync();
        List<DirtyAndAddWaterPoint> waterExcelList = EasyExcel.read(locationExcelFile).head(DirtyAndAddWaterPoint.class).sheet("排污点、加水点信息").doReadSync();
        //车辆信息
        catExcelList = EasyExcel.read(locationExcelFile).head(CarInfo.class).sheet("车辆信息").doReadSync();
        //车辆与加水点匹配信息
        List<CarMatchAddWaterPointInfo> carMatchAddWaterPointInfoList = getCarMatchAddWaterPointInfoInitData();
        //不同时间可用的排污点
        List<DirtyWaterPointInfo> dirtyWaterPointInfoList = getDirtyWaterPointInfoInitData();

        initNumberOfSides = roadExcelList.size();
        //获取边数
        AtomicInteger recordSide = new AtomicInteger();
        roadExcelList.forEach(o->{
            if (o.getRoadLength()==0){
                recordSide.getAndIncrement();
            }
        });
        /*
         *     arcs矩阵，记录每一个arc的
         *     0 编号 int
         *     1 出发点编号 int
         *     2 结束点编号 int
         *     3 弧一天要扫几次 int
         *     4 距离 w, 本处记录该路段长度（单位：km)，除以8得到洗扫时间，除以40得到正常走行时间,如果是点，则记为0
         *     6 洗扫速度，该弧的洗扫速度 int
         *     5 指针 inv， 指向该路所对应的反向路，如果是点，仍指向自己 int
         * */
        this.arcsArray = ArrayUtils.getTwoDimensionalArrayWithDirInitData(2*initNumberOfSides-recordSide.get(),7,1);
        int maxPoint1Number = roadExcelList.stream().sorted(Comparator.comparing(Road::getPoint1Number).reversed()).findFirst().get().getPoint1Number();
        int maxPoint2Number = roadExcelList.stream().sorted(Comparator.comparing(Road::getPoint2Number).reversed()).findFirst().get().getPoint2Number();
        this.nodes = ArrayUtils.getOneDimensionalArrayWithDirInitData(Math.max(maxPoint1Number,maxPoint2Number)+1,-1);
        Road[] roadArray = roadExcelList.toArray(new Road[roadExcelList.size()]);
        updateArcsArray(roadArray,initNumberOfSides);
        distanceArray = ArrayUtils.getTwoDimensionalArrayWithDirInitData(count+1,count+1,-1);
        updateDistanceArray(initNumberOfSides,roadArray);
        this.arcDistanceArray = ArrayUtils.getTwoDimensionalArrayWithDirInitData(arcsArray.length,arcsArray.length,-1);
        updateArcDistanceArray();
        required_arc = new ArrayList<>();
        for (int i =0;i<initNumberOfSides;i++){
            if (roadArray[i].getWashAndSweep()==1){
                required_arc.add(roadArray[i].getRoadNumber());
                required_arc.add(roadArray[i].getRoadNumber()+1000);
            }
        }
        counst_required = new ArrayList<>();
        required_arc.forEach(o->{counst_required.add(o);});
        CarInfo[] carsArray = catExcelList.toArray(new CarInfo[0]);
        AP1 = carMatchAddWaterPoint2Array(carMatchAddWaterPointInfoList);
        IF = getPointDirtyWaterArray(dirtyWaterPointInfoList.stream().filter(o->o.isAllDayPush()==true).findFirst().get());
        IF1 = getPointDirtyWaterArray(dirtyWaterPointInfoList.stream().filter(o->o.isAllDayPush()==false).findFirst().get());
        lamdaap =getAddWaterTimeArray(carsArray);
        lamdaif =getSewageTimeArray(carsArray);
        Q1 = getDirtyWaterCapacityDesc(carsArray);
        Q2 = getCleanWaterCapacityDesc(carsArray);
        all_arc = getArcsArrayFirstCowList();
        cind_required_arc = getCindRequiredArcList(all_arc);
        ind_required_arc = getIndRequiredArcList();
        ind_depot = all_arc.indexOf(depot.doubleValue());
        ind_AP = getIndAPList();
        ind_IF = getIndIFList();
        ind_IF1 = getIndIF1List();
        initialize_T(Q1.length/2);
        calculateMergeSavingData();
        copySavingData();
        getCarType();
        initCalculateRouteData();
        calculateRoute();
        calculateEmpty();
        printTrip();
        printEmptyRate();
    }

    private void getTa(){
        for (int i=0;i<T1.size();i++){
            for (int j=0;j<T1.get(i).size();j++){
                for (int k=0;k<T1.get(i).get(j).size();k++){
                    if (T1.get(i).get(j).get(k)==-1){
                        ta=i;
                        return;
                    }
                }
            }
        }
    }

    private void calculateEmpty(){
        getTa();
        List<Double> tmpCost = new ArrayList<>();
        List<List<Integer>> tmpPap = new ArrayList<>();
        List<List<List<Integer>>> tmpT1 = new ArrayList<>();
        for (int i=0;i<ta;i++){
            tmpCost.add(bestcost.get(i));
            tmpPap.add(pap.get(i));
            tmpT1.add(T1.get(i));
        }
        bestcost = tmpCost;
        T1 = tmpT1;
        pap = tmpPap;
    }

    private double sub_cost(int a,int b){
        double Z = 0;
        Z+=miu_plus_ap(ind_depot, T1.get(a).get(0).get(0)) + lamdaap[a];
        for (int j=0;j<T1.get(a).get(b).size()-1;j++){
            Z += service_time(T1.get(a).get(b).get(j)) + dijkstra(T1.get(a).get(b).get(j), T1.get(a).get(b).get(j+1));
        }
        Z += service_time(T1.get(a).get(b).get(T1.get(a).get(b).size() - 1)) + lamdaif[a];
        if (pap.get(a).contains(b)){
            if (Z>1.5){
                Z += miu_plus_ap1(T1.get(a).get(b).get(T1.get(a).get(b).size() - 1) ,T1.get(a).get(b+1).get(0)) + lamdaap[a];
            }else {
                Z += miu_plus_ap(T1.get(a).get(b).get(T1.get(a).get(b).size() - 1) ,T1.get(a).get(b+1).get(0)) + lamdaap[a];
            }
        }else {
            if (b==T1.get(a).size()-1){
                b -=1;
            }
            if (Z>1.5){
                Z += miu_star_if1(T1.get(a).get(b).get(T1.get(a).get(b).size() - 1) ,T1.get(a).get(b+1).get(0));
            }else {
                Z += miu_star_if(T1.get(a).get(b).get(T1.get(a).get(b).size() - 1) ,T1.get(a).get(b+1).get(0));
            }
        }
        return Z;
    }

    private void getCarType(){
        for(double i:Q1){
            if (!typecar_list.contains(i)){
                typecar_list.add(i);
            }
        }
        sametypeDouble = typecar_list.stream().collect(Collectors.toList());
        typecar_list.forEach(o->{
            sametype.add((int)(Arrays.stream(Q1).filter(value->value.equals(o)).count()));
        });
    }

    /**
     * 模拟索引数据
     * */
    private void getIndexList(){
        indexList.addAll(Arrays.asList(0,0,1,0,3,1,0,5,1,0,0,1,0,3,1,0,11,3,1,0));
        indexList.addAll(Arrays.asList(4,0,0,0,0,0,0,1,0,1,0,8,1,1,3,2,3,2,0,0));
        indexList.addAll(Arrays.asList(0,4,0,1,0,0,4,0,0,13,8,1,1,2,1,0,0,7,3,3));
        indexList.addAll(Arrays.asList(1,10,1,1,0,0,1,0,1,1,0,7,0,1,0,1,25,20,2,2));
        indexList.addAll(Arrays.asList(1,0,0,2,2,1,1,0,1,0,0));

        indexList.addAll(Arrays.asList(0,0,0,0,0,1,0,0,6,0,0,1,0,3,1,0,0,1,0,1));
        indexList.addAll(Arrays.asList(2,0,0,0,10,8,0,1,5,0,0,0,0,0,0,8,3,2,0,2));
        indexList.addAll(Arrays.asList(0,1,2,0,6,2,0,1,0,0,0));
    }

    /**
     * super interval
     * */
    private void calculateRoute(){
        while (required_arc.size()!=0){
            List<Integer> ind_required_arc_seq = new ArrayList<>();
            for (int i = 0;i<required_arc.size();i++){
                int index = all_arc.indexOf(new Double(required_arc.get(i)));
                if (index!=-1) {
                    ind_required_arc_seq.add(index);
                }
            }
            if (ind_required_arc_seq.size()>0){
                ind_required_arc = ind_required_arc_seq;
            }
            int ind_depot_index = all_arc.indexOf(new Double(depot));
            if (ind_depot_index!=-1) {
                ind_depot = ind_depot_index;
            }
            List<Integer> ind_AP_seq = new ArrayList<>();
            for (int i =0;i<AP1[x].length;i++){
                int index = all_arc.indexOf(new Double(AP1[x][i]));
                if (index!=-1) {
                    ind_AP_seq.add(index);
                }
            }
            if (ind_AP_seq.size()>0){
                ind_AP = ind_AP_seq;
            }
            List<Integer> ind_IF_seq = new ArrayList<>();
            for (int i = 0;i<IF.length;i++){
                int index = all_arc.indexOf(IF[i]);
                if(index!=-1) {
                    ind_IF_seq.add(index);
                }
            }
            if (ind_IF_seq.size()>0){
                ind_IF = ind_IF_seq;
            }
            List<Integer> ind_IF1_seq = new ArrayList<>();
            for (int i =0;i<IF1.length;i++){
                int index = all_arc.indexOf(new Double(IF1[i]));
                if (index!=-1) {
                    ind_IF1_seq.add(index);
                }
            }
            if (ind_IF1_seq.size()>0){
                ind_IF1 = ind_IF1_seq;
            }
            water_load = new ArrayList<>();
            T = new ArrayList<>();
            initialize_T(x);
            P_AP = new ArrayList<>();
            for (int i =0;i<T.size();i++){
                P_AP.add(new ArrayList<>());
            }
            count = 2;
            List<List<List<Integer>>> const_T = T;
            List<List<Integer>> const_P_AP = P_AP;
            double best_cost = 100;
            List<List<List<Integer>>> best_solution = new ArrayList<>();
            List<List<Integer>> best_AP = new ArrayList<>();
            while (count>0){
                count -= 1;
                Random random = new Random();
                random.setSeed(count);
                double cost = 0;
                T = const_T;
                P_AP = const_P_AP;
                for (double m :map_){
                    List<List<Integer>> arc_map = new ArrayList<>();
                    for (int i =0 ;i<dict_m.size();i++){
                        if (!dict_m.get(i).containsKey(m)){
                            dict_m.get(i).put(m,new ArrayList<>());
                        }
                        arc_map.addAll(dict_m.get(i).get(m));
                    }
                    while (arc_map.size()>0){
                        int merge = 0;
                        for (List<Integer> o :arc_map){
                            int u = o.get(0);
                            int v = o.get(1);
                            int i = get_Ind(u);
                            int j = get_Ind(v);
                            int temp = 0;

                            if (j==-1){
                                if (P_AP.get(P_AP.size()-1).size()==0){
                                    temp = T.get(T.size()-1).size();
                                }else {
                                    temp = P_AP.get(P_AP.size()-1).get(0);
                                }
                            }else {
                                if (P_AP.get(j).size()==0){
                                    temp = T.get(j).size();
                                }else {
                                    temp = P_AP.get(j).get(0);
                                }
                            }
                            if (i == -1 || j == -1){
                                merge=0;
                            }else if (u!=T.get(i).get(T.get(i).size()-1).get(T.get(i).get(T.get(i).size()-1).size()-1)||
                                    v!=T.get(j).get(0).get(0)){
                                merge=0;
                            }else if (i==j){
                                merge=0;
                            }else if (time_cost(i)+time_cost(j)-m>L){
                                merge=0;
                            }else if (intsInListInt(u,v,dict_m.get(0).get(m)) &&
                                    (load(i,T.get(i).size()-1)+ load(j,0)>Q1[x] ||water_load.get(i)-getSumByLoad(j,temp)<0)){
                                merge=0;
                            }else if(intsInListInt(u,v,dict_m.get(1).get(m))&&water_load.get(i)-getSumByLoad(j,temp)<0){
                                merge=0;
                            }else {
                                merge=1;
                            }
                            if (merge==0&&intsInListInt(u,v,dict_m.get(0).get(m))){
                                int index = getIndexFromDict_m(u,v,dict_m.get(0).get(m));
                                dict_m.get(0).get(m).remove(index);
                            }else if (merge==0&&intsInListInt(u,v,dict_m.get(1).get(m))){
                                int index = getIndexFromDict_m(u,v,dict_m.get(1).get(m));
                                dict_m.get(1).get(m).remove(index);
                            }else if (merge==0&&intsInListInt(u,v,dict_m.get(2).get(m))){
                                int index = getIndexFromDict_m(u,v,dict_m.get(2).get(m));
                                dict_m.get(2).get(m).remove(index);
                            }
                        }
                        arc_map = new ArrayList<>();
                        for (int i= 0 ;i<dict_m.size();i++){
                            arc_map.addAll(dict_m.get(i).get(m));
                        }
                        if (arc_map.size()>0){
                            int ind = indexList.get(index_tmp);
                                    //random.nextInt(arc_map.size());  //indexList.get(index_tmp);
                            index_tmp+=1;
                            int u = 0;
                            try {
                                u = arc_map.get(ind).get(0);
                            }catch (Exception ex){
                                log.error("");
                            }
                            int v = arc_map.get(ind).get(1);
                            int i = get_Ind(u);
                            int j = get_Ind(v);
                            if (P_AP.size()==4){
                                log.info("");
                            }
                            if (intsInListInt(u,v,dict_m.get(0).get(m))){
                                if (P_AP.get(j).size()==0){
                                    water_load.set(i,water_load.get(i) - getSumByLoad(j,T.get(j).size()));
                                }else {
                                    water_load.set(i,water_load.get(j));
                                }
                                List<Integer> listTmp = new ArrayList<>();
                                P_AP.get(i).forEach(o->{
                                    listTmp.add(o);
                                });
                                listTmp.addAll(getP_APList(T.get(i).size(),P_AP.get(j),P_AP.get(j).size()));
                                P_AP.set(i,listTmp);
                                List<Integer> r1 = new ArrayList<>();
                                T.get(i).get(T.get(i).size() - 1).forEach(o->{
                                    r1.add(o);
                                });
                                List<Integer> r2 = new ArrayList<>();
                                T.get(j).get(0).forEach(o->{
                                    r2.add(o);
                                });
                                r1.addAll(r2);
                                T.get(i).set(T.get(i).size()-1,r1);
                                T.get(j).remove(T.get(j).get(0));
                                List<List<Integer>> t1 = T.get(i).stream().collect(Collectors.toList());
                                List<List<Integer>> t2 = T.get(j).stream().collect(Collectors.toList());
                                t1.addAll(t2);
                                T.set(i,t1);
                            }
                            else if (intsInListInt(u,v,dict_m.get(1).get(m))){
                                if (P_AP.get(j).size()==0){
                                    water_load.set(i,water_load.get(i) - getSumByLoad(j,T.get(j).size()));
                                }else {
                                    water_load.set(i,water_load.get(j));
                                }
                                List<Integer> p_ap_tmp = new ArrayList<>();
                                P_AP.get(i).forEach(o->{
                                    p_ap_tmp.add(o);
                                });
                                P_AP.set(i,p_ap_tmp);
                                List<List<Integer>> t1 = T.get(i).stream().collect(Collectors.toList());;
                                List<List<Integer>> t2 = T.get(j).stream().collect(Collectors.toList());;
                                t1.addAll(t2);
                                T.set(i,t1);
                            }
                            else if (intsInListInt(u,v,dict_m.get(2).get(m))){
                                water_load.set(i,water_load.get(j));
                                List<Integer> p_ap_tmp = new ArrayList<>();
                                P_AP.get(i).forEach(o->{
                                    p_ap_tmp.add(o);
                                });
                                p_ap_tmp.add(T.get(i).size()-1);
                                p_ap_tmp.addAll(getP_APList(T.get(i).size()-1,P_AP.get(j),P_AP.get(j).size()));
                                P_AP.set(i,p_ap_tmp);
                                List<List<Integer>> t1 = T.get(i).stream().collect(Collectors.toList());;
                                List<List<Integer>> t2 = T.get(j).stream().collect(Collectors.toList());;
                                t1.addAll(t2);
                                T.set(i,t1);
                            }
                            T.set(j,new ArrayList<>());
                            T.remove(j);
                            water_load.set(j,new Double(0));
                            water_load.remove(j);
                            List<Integer> p_apTmp = new ArrayList<>();
                            p_apTmp.add(-1);
                            P_AP.set(j,p_apTmp);
                            P_AP.remove(j);
                        }
                    }
                }
                for (int i = 0 ;i< T.size();i++){
                    cost += time_cost(i);
                }
                if (cost<best_cost){
                    best_solution = T;
                    best_AP = P_AP;
                    best_cost = cost;
                }
            }
            for (int i = 0;i <sametype.get(x);i++){
                if (required_arc.size()!=0){
                    pap.set(t, P_AP.get(i));
                    T1.set(t, T.get(i));
                    bestcost.set(t, time_cost(i));
                    for (List<Integer> q: T.get(i)){
                        for (int w :q){
                            required_arc.remove(counst_required.get(cind_required_arc.indexOf(w)));
                        }
                    }
                    t+=1;
                }
            }
            dict_m1 = ArrayUtils.clone(cdm1);
            dict_m2 = ArrayUtils.clone(cdm2);
            dict_m3 = ArrayUtils.clone(cdm3);
            BeanUtils.copyProperties(cm1,map_1);
            BeanUtils.copyProperties(cm2,map_2);
            BeanUtils.copyProperties(cm3,map_3);
            dict_m = new ArrayList<>();
            dict_m.add(dict_m1);
            dict_m.add(dict_m2);
            dict_m.add(dict_m3);
            map_ = new ArrayList<>();
            map_.addAll(map_1);
            map_.addAll(map_2);
            map_.addAll(map_3);
            map_.sort(Collections.reverseOrder());
            x += 1;
        }
    }

    private List<Integer> getP_APList(int baseInt,List<Integer> P_APList,int range){
        List<Integer> result = new ArrayList<>();
        for (int n =0;n<range;n++){
            result.add(P_APList.get(n)+ baseInt);
        }
        return result;
    }

    /**
     * 获取T所在三维数组的索引
     * */
    private int get_Ind(int value){
        int index = -1;
        for (int i = 0;i<T.size();i++){
            if (T.get(i).size()==0){
                continue;
            }
            int size = T.get(i).size();
            int subSize = T.get(i).get(size-1).size();
            if (T.get(i).get(0).get(0)==value || T.get(i).get(size-1).get(subSize-1)==value){
                index =i;
                break;
            }
        }
        return index;
    }

    private int getIndexFromDict_m(int x,int y,List<List<Integer>> list){
        int index = 0;
        for (List<Integer> integerList:list){
            if (integerList.get(0)==x && integerList.get(1)==y){
                break;
            }
            index +=1;
        }
        return index;
    }

    private double getSumByLoad(int j ,int n){
        double result = 0;
        for (int index = 0;index<n;index++){
            result+=load(j, index);
        }
        return result;
    }

    private boolean intsInListInt(int i,int j ,List<List<Integer>> list){
        boolean result = false;
        for (List<Integer> sub :list){
            if (sub.get(0)==i&&sub.get(1)==j){
                result = true;
                break;
            }
        }
        return result;
    }

    private double load(int i,int j){
        double load = 0;
        for (int n = 0 ;n<T.get(i).get(j).size();n++) {
            int ind = T.get(i).get(j).get(n);
            load += arcsArray[ind][4];
        }
        return load;
    }

    /**
     * 这是一段很酸爽的代码
     * */
    private double time_cost(int ind_trip){
        double Z = 0;
        int tag = 0;
        Z += miu_plus_ap(ind_depot, T.get(ind_trip).get(0).get(0)) + lamdaap[x];
        for (int i=0;i<T.get(ind_trip).size();i++){
            if (tag>1){
                return Z;
            }
            for (int j =0;j<T.get(ind_trip).get(i).size()-1;j++){
                Z += service_time(T.get(ind_trip).get(i).get(j)) + dijkstra(T.get(ind_trip).get(i).get(j), T.get(ind_trip).get(i).get(j+1));
            }
            Z+=service_time(T.get(ind_trip).get(i).get(T.get(ind_trip).get(i).size()-1))+lamdaif[x];
            if (P_AP.get(ind_trip).contains(i)){
                if (Z>1.5){
                    Z += miu_plus_ap1(T.get(ind_trip).get(i).get(T.get(ind_trip).get(i).size() - 1) ,T.get(ind_trip).get(i+1).get(0)) + lamdaap[x];
                }else {
                    try{
                    Z += miu_plus_ap(T.get(ind_trip).get(i).get(T.get(ind_trip).get(i).size() - 1) ,T.get(ind_trip).get(i+1).get(0)) + lamdaap[x];
                    }catch (Exception e){
                    log.info("");
                    }
                }
            }
            else {
                if (T.get(ind_trip).size()-1==i){
                    i-=1;
                    tag+=1;
                }
                if (Z>1.5){
                    //处理i为-1的时候的越界问题
                    if (i==-1) {
                        Z += miu_star_if1(T.get(ind_trip).get(0).get(T.get(ind_trip).get(0).size() - 1), T.get(ind_trip).get(0).get(0));
                        break;
                    }else {
                        Z += miu_star_if1(T.get(ind_trip).get(i).get(T.get(ind_trip).get(i).size() - 1), T.get(ind_trip).get(i + 1).get(0));
                        if (tag>0){
                            break;
                        }
                    }
                }else {
                    //处理i为-1的时候的越界问题
                    if (i == -1) {
                        Z += miu_star_if(T.get(ind_trip).get(0).get(T.get(ind_trip).get(0).size() - 1), T.get(ind_trip).get(0).get(0));
                        break;
                    }else {
                        Z += miu_star_if(T.get(ind_trip).get(i).get(T.get(ind_trip).get(i).size() - 1), T.get(ind_trip).get(i + 1).get(0));
                        if (tag>0){
                            break;
                        }
                    }
                }
            }
        }
        Z += miu_star_if(T.get(ind_trip).get(T.get(ind_trip).size()-1).get(T.get(ind_trip).get(T.get(ind_trip).size()-1).size()-1) ,ind_depot);
        return Z;
    }

    /**
     * 初始化super interval所需要的参数
     * */
    private void initCalculateRouteData(){
        x = 0;
        t = 0;
        for (CarInfo carInfo : catExcelList){
            bestcost.add((double) -1);
            pap.add(Collections.singletonList(-1));
            List<Integer> subT1 = new ArrayList<>();
            for (int index = 0 ;index<20;index++){
                subT1.add(-1);
            }
            List<List<Integer>> sub = new ArrayList<>();
            sub.add(subT1);
            T1.add(sub);
        }
    }

    private void copySavingData(){
        cdm1 = ArrayUtils.clone(dict_m1);
        cdm2 = ArrayUtils.clone(dict_m2);
        cdm3 = ArrayUtils.clone(dict_m3);
        BeanUtils.copyProperties(cm1,map_1);
        BeanUtils.copyProperties(cm2,map_2);
        BeanUtils.copyProperties(cm3,map_3);
        cdm.add(cdm1);
        cdm.add(cdm2);
        cdm.add(cdm3);
        cm.addAll(cm1);
        cm.addAll(cm2);
        cm.addAll(cm3);
        cm.sort(Collections.reverseOrder());
    }

    private void calculateMergeSavingData(){
        for (int u:ind_required_arc ){
            for (int v:ind_required_arc){
                if (u==v||v==arcsArray[u][5]){
                    continue;
                }
                double m1 = miu_star_if(u,ind_depot) + dijkstra(ind_depot,best_AP_ind(ind_depot, v)) + dijkstra(best_AP_ind(ind_depot, v), v)+ lamdaap[Q1.length/2] + lamdaif[Q1.length/2] - dijkstra(u, v);
                List<Integer> list = new ArrayList<>();
                list.add(u);
                list.add(v);
                if (!map_1.contains(m1)){
                    map_1.add(m1);
                    List<List<Integer>> newList = new ArrayList<>();
                    newList.add(list);
                    dict_m1.put(m1,newList);
                }else {
                    List<List<Integer>> containsList = dict_m1.get(m1);
                    containsList.add(list);
                    dict_m1.put(m1,containsList);
                }
                double m2 = miu_star_if(u, ind_depot) + dijkstra(ind_depot, best_AP_ind(ind_depot, v)) + dijkstra(best_AP_ind(ind_depot, v), v)+ lamdaap[Q1.length/2] - miu_star_if(u, v);
                if (!map_2.contains(m2)){
                    map_2.add(m2);
                    List<List<Integer>> newList = new ArrayList<>();
                    newList.add(list);
                    dict_m2.put(m2,newList);
                }else {
                    List<List<Integer>> containsList = dict_m2.get(m2);
                    containsList.add(list);
                    dict_m2.put(m2,containsList);
                }
                double m3 = miu_star_if(u, ind_depot) + dijkstra(ind_depot, best_AP_ind(ind_depot, v)) + dijkstra(best_AP_ind(ind_depot, v), v) - miu_plus_ap(u, v);
                if (!map_3.contains(m3)){
                    map_3.add(m3);
                    List<List<Integer>> newList = new ArrayList<>();
                    newList.add(list);
                    dict_m3.put(m3,newList);
                }else {
                    List<List<Integer>> containsList = dict_m3.get(m3);
                    containsList.add(list);
                    dict_m3.put(m3,containsList);
                }
            }
        }
        dict_m.add(dict_m1);
        dict_m.add(dict_m2);
        dict_m.add(dict_m3);
        map_.addAll(map_1);
        map_.addAll(map_2);
        map_.addAll(map_3);
        map_.sort(Collections.reverseOrder());
    }

    /**
     * 弧u到最优加水点再到v所需时间
     * */
    private double miu_plus_ap(int  u,int v){
        double dis_1 = arcDistanceArray[u][best_AP_ind(u,v)] + nonservice_speed*miu_star_if(best_AP_ind(u, v), v);
        double dis_2 = nonservice_speed*miu_star_if(u, best_AP_ind(u, v)) + arcDistanceArray[best_AP_ind(u, v)][v];
        return Math.min(dis_1,dis_2)/nonservice_speed;
    }

    private double miu_plus_ap1(int u,int v){
        double dis_1 = arcDistanceArray[u][best_AP_ind(u, v)] + nonservice_speed*miu_star_if1(best_AP_ind(u, v), v);
        double dis_2 = nonservice_speed*miu_star_if1(u, best_AP_ind(u, v)) + arcDistanceArray[best_AP_ind(u, v)][v];
        return Math.min(dis_1,dis_2)/nonservice_speed;
    }

    /**
     * u到v的非服务时间
     * */
    private double dijkstra(int u,int v){
        return arcDistanceArray[u][v]/nonservice_speed;
    }

    /**
     * u的服务时间
     * */
    private double service_time(int u){
        return arcsArray[u][4] / arcsArray[u][6];
    }

    /**
     * 弧u到最优排污点再到v所需时间
     * */
    private double miu_star_if(int u,int v){
        return (arcDistanceArray[u][best_IF(u,v)]+arcDistanceArray[best_IF(u,v)][v])/nonservice_speed;
    }

    private double miu_star_if1(int u,int v){
        return (arcDistanceArray[u][best_IF1(u, v)] + arcDistanceArray[best_IF1(u, v)][v])/nonservice_speed;
    }

    /**
     * 求两弧间最优的排污点
     * */
    private int best_IF(int u,int v){
        List<Double> dis = new ArrayList<>();
        ind_IF.forEach(o-> dis.add((arcDistanceArray[u][o] + arcDistanceArray[o][v])));
        int min_index = dis.indexOf(Collections.min(dis));
        return ind_IF.get(min_index);
    }

    /**
     * 求两弧间最优的8点之后排污点
     * */
    private int best_IF1(int u,int v){
        List<Double> dis = new ArrayList<>();
        ind_IF1.forEach(o->{
            dis.add((arcDistanceArray[u][o] + arcDistanceArray[o][v]));
        });
        int min_index = dis.indexOf(Collections.min(dis));
        return ind_IF1.get(min_index);
    }

    private int best_AP_ind(int u,int v){
        List<Double> dis = new ArrayList<>();
        ind_AP.forEach(o->{
            dis.add((arcDistanceArray[u][o] + arcDistanceArray[o][v]));
        });
        int min_index = dis.indexOf(Collections.min(dis));
        return ind_AP.get(min_index);
    }

    private void updateArcDistanceArray(){
        for (int oarc= 0 ;oarc<arcsArray.length;oarc++){
            for (int darc = 0;darc<arcsArray.length;darc++){
                if (arcDistanceArray[oarc][darc]<0){
                    int o = (int)nodes[(int) arcsArray[oarc][2]];
                    int d = (int)nodes[(int) arcsArray[darc][1]];
                    double dis = distanceArray[o][d];
                    arcDistanceArray[oarc][darc] = dis;
                }
            }
        }
    }

    private void initialize_T(int initData){
        ind_required_arc.forEach(o->{
            List<List<Integer>> mainRoute = new ArrayList<>();
            water_load.add(Q2[initData] - arcsArray[o][4]);
            List<Integer> route = new ArrayList<>();
            route.add(o);
            mainRoute.add(route);
            T.add(mainRoute);
        });
    }

    private List<Integer> getIndIFList(){
        List<Integer> result = new ArrayList<>();
        for (int index = 0 ;index < IF.length;index++){
            Double IF_value = IF[index].doubleValue();
            int tag = all_arc.indexOf(IF_value);
            if (tag!=-1){
                result.add(tag);
            }
        }
        return result;
    }

    private List<Integer> getIndIF1List(){
        List<Integer> result = new ArrayList<>();
        for (int index = 0 ;index < IF1.length;index++){
            Double IF_value = IF1[index].doubleValue();
            int tag = all_arc.indexOf(IF_value);
            if (tag!=-1){
                result.add(tag);
            }
        }
        return result;
    }

    private List<Integer> getIndAPList(){
        List<Integer> result = new ArrayList<>();
        int size = AP1[Q1.length /2].length;
        for (int index = 0;index<size;index++){
            Double AP1_value = AP1[Q1.length /2][index].doubleValue();
            int tag = all_arc.indexOf(AP1_value);
            if (tag!=-1){
                result.add(tag);
            }
        }
        return result;
    }


    private List<Integer> getCindRequiredArcList(List<Double> all_arc){
        List<Integer> result = new ArrayList<>();
        Object[] counst_required_array = counst_required.toArray();
        for (int index =0;index<counst_required.size();index++){
            Double counst_required_array_value = ((Integer) counst_required_array[index]).doubleValue();
            int tag = all_arc.indexOf(counst_required_array_value);
            if (tag!=-1){
                result.add(tag);
            }
        }
        return result;
    }

    private List<Integer> getIndRequiredArcList(){
        List<Integer> result = new ArrayList<>();
        Object[] required_arc_array = required_arc.toArray();
        for (int index = 0;index<required_arc_array.length;index++){
            Double required_array_value = ((Integer) required_arc_array[index]).doubleValue();
            int tag = all_arc.indexOf(required_array_value);
            if (tag!=-1){
                result.add(tag);
            }
        }
        return result;
    }

    /**
     * 获取ArcsArray的第一列
     * */
    private List<Double> getArcsArrayFirstCowList(){
        List<Double> cowList = new ArrayList<>();
        for(int index = 0;index<arcsArray.length;index++){
            cowList.add(arcsArray[index][0]);
        }
        return cowList;
    }

    /**
     * 初始化车辆与加水点匹配信息数据
     * */
    private List<CarMatchAddWaterPointInfo> getCarMatchAddWaterPointInfoInitData(){
        List<CarMatchAddWaterPointInfo> carMatchAddWaterPointInfoList = new ArrayList<>();
        for (int i=1;i<11;i++){
            CarMatchAddWaterPointInfo carMatchAddWaterPointInfo = new CarMatchAddWaterPointInfo();
            carMatchAddWaterPointInfo.setCarNumber(i);
            List<Integer> waterPointList = new ArrayList<>();
            waterPointList.add(104);
            waterPointList.add(111);
            if (i!=2&&i!=3&&i!=4){
                waterPointList.add(118);
            }
            waterPointList.add(122);
            carMatchAddWaterPointInfo.setAddWaterPointNumberList(waterPointList);
            carMatchAddWaterPointInfoList.add(carMatchAddWaterPointInfo);
        }
        return carMatchAddWaterPointInfoList;
    }

    /**
    * 车辆与加水点匹配信息转换成二维数组
    * */
    private Integer[][] carMatchAddWaterPoint2Array(List<CarMatchAddWaterPointInfo> carMatchAddWaterPointInfoList){
        Integer[][] array = new Integer[carMatchAddWaterPointInfoList.size()][];
        CarMatchAddWaterPointInfo[] carMatchAddWaterPointInfoArray = carMatchAddWaterPointInfoList.toArray(new CarMatchAddWaterPointInfo[0]);
        for (int index = 0 ;index<carMatchAddWaterPointInfoArray.length;index++ ){
            Integer[] init = new Integer[carMatchAddWaterPointInfoArray[index].getAddWaterPointNumberList().size()];
            array[index] = carMatchAddWaterPointInfoArray[index].getAddWaterPointNumberList().toArray(init);
        }
        return array;
    }

    /**
     * 初始化不同时间点排污数据
     * */
    private List<DirtyWaterPointInfo> getDirtyWaterPointInfoInitData(){
        DirtyWaterPointInfo allDay = new DirtyWaterPointInfo();
        List<Integer> allDayPoints = new ArrayList<>();
        allDayPoints.add(101);
        allDayPoints.add(107);
        allDayPoints.add(115);
        allDayPoints.add(123);
        allDayPoints.add(124);
        allDay.setAllDayPush(true);
        allDay.setDirtyWaterPointNumberList(allDayPoints);
        DirtyWaterPointInfo notAllDay = new DirtyWaterPointInfo();
        List<Integer> notAllDayPoints = new ArrayList<>();
        notAllDayPoints.add(101);
        notAllDayPoints.add(107);
        notAllDayPoints.add(115);
        notAllDayPoints.add(123);
        notAllDay.setAllDayPush(false);
        notAllDay.setDirtyWaterPointNumberList(notAllDayPoints);
        List<DirtyWaterPointInfo> dirtyWaterPointInfoList = new ArrayList<>();
        dirtyWaterPointInfoList.add(allDay);
        dirtyWaterPointInfoList.add(notAllDay);
        return dirtyWaterPointInfoList;
    }

    /**
     * 将污水处理点编号处理成数组
     * */
    private Integer[] getPointDirtyWaterArray(DirtyWaterPointInfo dirtyWaterPointInfo){
        return dirtyWaterPointInfo.getDirtyWaterPointNumberList().toArray(new Integer[0]);
    }

    /**
     * 将车辆的排污时间转换成数组
     * */
    private Double[] getSewageTimeArray(CarInfo[] carInfoArray){
        Double[] array = new Double[carInfoArray.length];
        for (int index = 0 ;index < carInfoArray.length;index++){
            array[index] = carInfoArray[index].getEmissionDirtyWaterTime();
        }
        return array;
    }

    /**
     * 将车辆的加水时间转换成数组
     * */
    private Double[] getAddWaterTimeArray(CarInfo[] carInfoArray){
        Double[] array = new Double[carInfoArray.length];
        for (int index = 0 ;index < carInfoArray.length;index++){
            array[index] = carInfoArray[index].getAddCleanWaterTime();
        }
        return array;
    }

    /**
     * 获取污水箱容量
     * */
    private Double[] getDirtyWaterCapacityDesc(CarInfo[] carInfoArray){
        Double[] array = new Double[carInfoArray.length];
        for (int index =0;index<carInfoArray.length;index++){
            array[index] = carInfoArray[index].getDirtyWaterCapacity();
        }
        Arrays.sort(array, Collections.reverseOrder());
        return array;
    }

    /**
     * 获取清水箱容量
     * */
    private Double[] getCleanWaterCapacityDesc(CarInfo[] carInfoArray){
        Double[] array = new Double[carInfoArray.length];
        for (int index =0;index<carInfoArray.length;index++){
            array[index] = carInfoArray[index].getCleanWaterCapacity();
        }
        Arrays.sort(array, Collections.reverseOrder());
        return array;
    }

    /**
     * 更新
     * */
    private void updateDistanceArray(int initNumberOfSides,Road[] roadArray){
        for (int i = 0 ;i < initNumberOfSides ;i++){
            int p1 = roadArray[i].getPoint1Number();
            int p2 = roadArray[i].getPoint2Number();
            distanceArray[(int) nodes[p1]][(int) nodes[p2]] = roadArray[i].getRoadLength()/1000;
            distanceArray[(int) nodes[p2]][(int) nodes[p1]] = roadArray[i].getRoadLength()/1000;
        }
        for (int i =0;i<distanceArray.length;i++){
            for (int j = 0;j<distanceArray.length-1;j++){
                if (distanceArray[i][j]==-1){
                    distanceArray[i][j] = 100000;
                }
                distanceArray[i][i] = 0;
            }
        }
        for (int k =0;k<distanceArray.length;k++) {
            for (int i = 0; i < distanceArray.length - 1; i++) {
                for (int j = 0; j < distanceArray.length - 1; j++) {
                    distanceArray[i][j] = Math.min(distanceArray[i][j],(distanceArray[i][k]+distanceArray[k][j]));
                }
            }
        }
    }

    /**
     * 更新arcsArray
     * */
    private double[][] updateArcsArray(Road[] roadArray,int initNumberOfSides){
        int j =0;
        for (int index = 0;index<initNumberOfSides;index++){
            arcsArray[j][0] = roadArray[index].getRoadNumber();
            arcsArray[j][1] = roadArray[index].getPoint1Number();
            if (nodes[(int) arcsArray[j][1]]<0){
                nodes[(int) arcsArray[j][1]] = count;
                count += 1;
            }
            arcsArray[j][2] = roadArray[index].getPoint2Number();
            if (nodes[(int) arcsArray[j][2]]<0){
                nodes[(int) arcsArray[j][2]] = count;
                count += 1;
            }
            arcsArray[j][3] = roadArray[index].getFrequency();
            arcsArray[j][4] = roadArray[index].getRoadLength()/1000;
            arcsArray[j][6] = roadArray[index].getSpeed();
            if (roadArray[index].getRoadLength()>0){
                arcsArray[j][5] = j+1;
                j+=1;
                arcsArray[j][0] = roadArray[index].getRoadNumber()+1000;
                arcsArray[j][1] = roadArray[index].getPoint2Number();
                arcsArray[j][2] = roadArray[index].getPoint1Number();
                arcsArray[j][3] = roadArray[index].getFrequency();
                arcsArray[j][4] = roadArray[index].getRoadLength()/1000;
                arcsArray[j][5] = j-1;
                arcsArray[j][6] = roadArray[index].getSpeed();
                j+=1;
            }else {
                arcsArray[j][5] = j;
                j+=1;
            }
        }
        return arcsArray;
    }

    private int print_IF(int u,int v){
        List<Double> dis = new ArrayList<>();
        ind_IF.forEach(o->{
            dis.add(arcDistanceArray[u][o]+arcDistanceArray[o][v]);
        });
//        for (int index = 0 ;index<ind_IF.size();index++){
//            dis.add(arcDistanceArray[u][index]+arcDistanceArray[index][v]);
//        }
        double min =dis.stream().min(Double::compare).get();
        int min_index = dis.indexOf(min);
        int result = IF[min_index];
        log.info("{} 排污",result);
        return result;
    }
    private int print_IF1(int u,int v){
        List<Double> dis = new ArrayList<>();
        ind_IF1.forEach(o->{
            dis.add(arcDistanceArray[u][o]+arcDistanceArray[o][v]);
        });
//        for (int index = 0 ;index<ind_IF1.size();index++){
//            dis.add(arcDistanceArray[u][index]+arcDistanceArray[index][v]);
//        }
        double min =dis.stream().min(Double::compare).get();
        int min_index = dis.indexOf(min);
        int result = IF1[min_index];
        log.info("{} 排污",result);
        return result;
    }
    private int print_AP_IF(int u,int v){
        int result = 0;
        double dis1 = arcDistanceArray[u][best_AP_ind(u,v)]+miu_star_if(best_AP_ind(u,v), v);
        double dis2 = miu_star_if(u, best_AP_ind(u,v)) + arcDistanceArray[best_AP_ind(u,v)][v];
        if(dis1 > dis2){
            print_IF(u, best_AP_ind(u,v));
            log.info("{} 加水",best_AP_ind(u,v));
        }else {
            print_IF(best_AP_ind(u,v), v);
            log.info("{} 加水",best_AP_ind(u,v));
        }
        return result;
    }
    private int print_AP_IF1(int u,int v){
        int result = 0;
        double dis1 = arcDistanceArray[u][best_AP_ind(u,v)]+miu_star_if(best_AP_ind(u,v), v);
        double dis2 = miu_star_if(u, best_AP_ind(u,v)) + arcDistanceArray[best_AP_ind(u,v)][v];
        if(dis1 > dis2){
            print_IF1(u, best_AP_ind(u,v));
            log.info("{} 加水",best_AP_ind(u,v));
        }else {
            print_IF1(best_AP_ind(u,v), v);
            log.info("{} 加水",best_AP_ind(u,v));
        }
        return result;
    }
    private void printTrip(){
        for (int i = 0; i < T1.size();i++){
            log.info("trip: {}",i+1);
            log.info(0+ " 车场");
            log.info("离车场最近的加水点加水");
            for (int j = 0; j < T1.get(i).size();j++){
                for (int n =0;n< T1.get(i).get(j).size();n++){
                    if(arcsArray[T1.get(i).get(j).get(n)][0]>1000){
                        log.info("{} 反向",(int)arcsArray[T1.get(i).get(j).get(n)][0]-1000);
                    }else {
                        log.info((int)arcsArray[T1.get(i).get(j).get(n)][0]+"");
                    }
                }
                if (pap.get(i).contains(j)){
                    if (sub_cost(i,j) < 3.5){
                        print_AP_IF(T1.get(i).get(j).get(T1.get(i).get(j).size()-1) ,T1.get(i).get(j+1).get(0));
                    }else {
                        print_AP_IF1(T1.get(i).get(j).get(T1.get(i).get(j).size()-1) ,T1.get(i).get(j+1).get(0));
                    }
                }
                else if (j == T1.get(i).size()-1){
                    print_AP_IF(T1.get(i).get(j).get(T1.get(i).get(j).size()-1) ,ind_depot);
                }
                else {
                    if (sub_cost(i,j) < 3.5){
                        print_IF(T1.get(i).get(j).get(T1.get(i).get(j).size()-1) ,T1.get(i).get(j+1).get(0));
                    }else {
                        print_IF1(T1.get(i).get(j).get(T1.get(i).get(j).size()-1) ,T1.get(i).get(j+1).get(0));
                    }
                }
            }
        }
    }
    private void printEmptyRate(){
        int k1 = 0;
        int k2 = 0;
        for (int i = 0;i<T1.size();i++){
            for (int j = 0;j<T1.get(i).size()-1;j++){
                k1+=1;
            }
        }
        for (int i = 0 ;i<pap.size();i++){
            for (int j=0;j<pap.get(i).size();j++){
                k2+=1;
            }
        }
        required_arc = new ArrayList<>();
        roadExcelList.forEach(o->{
            if (o.getWashAndSweep()==1){
                required_arc.add(o.getRoadNumber());
                required_arc.add(o.getRoadNumber()+1000);
            }
        });
        ind_required_arc = new ArrayList<>();
        for(int i = 0; i<required_arc.size();i++){
            ind_required_arc.add(all_arc.indexOf(new Double(required_arc.get(i))));
        }
        double empty_dis = (getBestcostSum()- 0.34*(2*T1.size()+k1+k2)-getind_required_arcSum()) * nonservice_speed;
        double true_dis = 0;
        for (int i = 0;i<ind_required_arc.size();i++){
            true_dis+=arcsArray[ind_required_arc.get(i)][4];
        }
        double total_dis = empty_dis + true_dis;
        double empty_rate = empty_dis / total_dis;
        log.info(true_dis+"");
        log.info(total_dis+"");
        log.info(empty_rate+"");
    }

    private double getBestcostSum(){
        double result = 0 ;
        for (int i =0 ;i<bestcost.size();i++){
            result+=bestcost.get(i);
        }
        return result;
    }

    private double getind_required_arcSum(){
        double result = 0;
        for (int i =0 ;i<ind_required_arc.size();i++){
            result += arcsArray[ind_required_arc.get(i)][ 4]/arcsArray[ind_required_arc.get(i)][ 6];
        }
        return result;
    }
}